home *** CD-ROM | disk | FTP | other *** search
/ Acorn User: China / Acorn User China CD-ROM (UK) (Disc B) / Acorn User China CD-ROM (UK) (Disc B).bin / STUTTGART / MATHS / LABYRINTH / !Labyrinth_!Help < prev    next >
Encoding:
Text File  |  1995-01-06  |  12.5 KB  |  248 lines
  1. --------------------------------------------------------------------------
  2.                             !Labyrinth
  3. --------------------------------------------------------------------------
  4.  
  5.                              Version: 2.17, (05.01.95)
  6.                               RiscOS: mindestens V2.00
  7.                                  RAM: 160 Kbytes
  8.                                Autor: Stefan Tomlik
  9.  
  10.   !Labyrinth ist PUBLIC DOMAIN und darf frei kopiert, verbreitet, verändert
  11. und benutzt werden. Es ist nicht erlaubt, außer zum Zweck der Aufwands-
  12. entschädigung oder der Begleichung von Versandskosten irgendeinen
  13. Geldbetrag zu berechnen.
  14.  
  15.  
  16. --------------------------------------------------------------------------
  17.                              Benutzung
  18. --------------------------------------------------------------------------
  19.  
  20.   Nach dem Start von !Labyrinth werden Sie aufgefordert, die Größe des
  21. Labyrinth-Feldes festzulegen. Dieser Wert muß innerhalb der vom Programm
  22. genannten Grenzen liegen. Es wird dann ein quadratisches Feld generiert,
  23. dessen Kantenlänge der gewünschten Größe entspricht. (Zur Struktur des
  24. generierten Feldes siehe 'Datenstruktur des Labyrinths'). Direkt nach der
  25. Generierung werden Start- und Endpunkt im Feld zufällig festgelegt und ein
  26. Weg vom Start- zum Endpunkt gesucht. (siehe 'Aufbau der graphischen
  27. Demonstration') Wenn ein möglicher Weg gefunden wurde, läßt Sie das der
  28. Rechner durch einen Piepton wissen. Danach fragt das Programm mittels
  29. OS_Confirm, ob ein weiteres Labyrinth generiert werden soll (Antwort
  30. per Maus: SELECT = Ja, MENU oder ADJUST = Nein).
  31.  
  32. --------------------------------------------------------------------------
  33.                             Beschreibung
  34. --------------------------------------------------------------------------
  35.  
  36.   !Labyrinth ist eine graphische Demonstration der Arbeitsweise eines
  37. Backtracking-Algorithmus zur Lösung von beliebigen Labyrinthen. Es wurde mit
  38. Acorn's ISO Pascal Compiler (V2.2.2) geschrieben. Zur Kompilation werden
  39. einige Routinen aus der ISO Pascal Extension Library 'xLib' Release 2.00
  40. benötigt (© 1990, 1991 Nick Smith). Aus rechtlichen Gründen ist es mir nicht
  41. möglich, diese Library beizulegen, die Routinen dürften allerdings
  42. problemlos ersetzbar sein:
  43.  
  44. IMPORT Procedure Bell;
  45.   Ausgabe eines ASCII Standard 'Beep'-Sounds
  46.  
  47. IMPORT Procedure Hourglass_On;
  48. IMPORT Procedure Hourglass_Off;
  49. IMPORT Procedure Hourglass_Percentage (percen: Integer);
  50.   Dazu muß man wohl nicht viel schreiben.
  51.  
  52. IMPORT Procedure Cursor_Off;
  53.   Equivalent zu *SWI_OS_RemoveCursors
  54.  
  55. IMPORT Procedure Cursor_On;
  56.   Equivalent zu *SWI_OS_RestoreCursors
  57.  
  58. IMPORT Function  OS_Confirm: Char;
  59.   mögliche Ergebnisse: 'y' für SELECT oder 'n' für irgend eine
  60.   andere Eingabe. Tastatureingaben werden auch interpretiert.
  61.  
  62. IMPORT Procedure Gcol (plotMode, col: Integer);
  63.   Equivalent zu BASIC's GCOL-Befehl
  64.  
  65. IMPORT Procedure Plot (command, xpos, ypos: Integer);
  66.   Equivalent zu 'PLOT' in BASIC und dem 'OS_Plot'-SWI. Übergeben
  67.   werden ein Plot-Code und die dazugehörigen Koordinatenparameter.
  68.  
  69. IMPORT Procedure Move (x, y: Integer);
  70.   (x, y sind absolute Koordinaten (relativ zum Koordinatenursprung)
  71.  
  72. IMPORT Procedure Draw (x, y: Integer);
  73.   (x, y sind relative Koordinaten zur Position des Graphic-Cursors)
  74.  
  75. IMPORT Procedure Line (x1, y1, x2, y2: Integer);
  76.   (x1, y1, x2, y2 sind absolute Koordinaten. Benötigt 'Move' )
  77.  
  78. IMPORT Function Rnd (VAR seed: integer): Real;
  79.   Diese Funktion ergibt die nächste Zahl aus einer einheitlich ver-
  80.   teilten pseudozufälligen Sequenz im Bereich 0.0 <= Rnd < 1.0.
  81.   Die 'x-Lib'-Implementation benötigt dazu eine globale Konstante
  82.   'startSeed' = 49631 und eine globale Variable 'seed', die zu
  83.   Anfang des Programms (in diesem Program, mittels der standardisierten
  84.   'Randomize'-Prozedur) auf den Wert von 'startSeed' initialisiert
  85.   werden muß. Diese Variable darf dann nicht mehr (außer durch 'Rnd')
  86.   geändert werden.
  87.  
  88. IMPORT Function Random (low, high: Integer; VAR seed: integer): Integer;
  89.   Benötigt 'Rnd'. Das Funktionsergebnis ist ein Integerwert im Bereich
  90.   [low..high] (einschließlich).
  91.  
  92.  
  93. --------------------------------------------------------------------------
  94.                    Datenstruktur des Labyrinths (tLab)
  95. --------------------------------------------------------------------------
  96.  
  97.   Const
  98.     up = 1; right = 2; down = 4; left = 8;
  99.   Type
  100.     tLab = Array[0..maxSize,0..maxSize] Of Record
  101.       w: Byte;    { beschreibt die 'Wände' eines Elementes  }
  102.       v: Boolean; { (v)isited-Flag; benötigt von 'Possible' }
  103.     End; { tLab }
  104.  
  105.   Der '.w'-Eintrag beinhaltet Informationen darüber, ob an dieser
  106. Stelle des Labyrinths eine 'Wand' ist oder nicht. Dazu werden die
  107. Konstanten 'up' bis 'left' benötigt.
  108.  
  109.       lab[x,y].w := RandomInt(5);
  110.  
  111. Function RandomInt (max: Integer): Integer; { RandomInt = [0..max-1] }
  112.  
  113.   Der '.v'-Eintrag des beschriebenen Datenverbundes wird vom
  114. eigentlichen Lösungsalgorithmus 'Possible' benötigt, um festzuhalten,
  115. welche Positionen des Labyrinths' schon 'besucht' (visited) wurden.
  116. Dies war notwendig, um zu verhindern, daß der Algorithmus im
  117. ungünstigsten Falle in einer Endlosschleife hängen bleibt.
  118.  - Zu diesem Problem siehe BUGS & FEATURES ....
  119.  
  120. --------------------------------------------------------------------------
  121.              Prioritätenregelung des Suchvorgangs (tPrioTab)
  122. --------------------------------------------------------------------------
  123.  
  124.   Type
  125.     tPrioTab = Array[1..4] Of Record
  126.       go: Byte;        { eine/mehrere der Richtungen 'up' - 'left' (s.o) }
  127.       ox, oy: Integer; { die dazu benötigen Offsets (s.u.)               }
  128.     End; { tPrioTab }
  129.  
  130.   Der Lösungsalgorithmus arbeitet Backtracking-orientiert. Eine
  131. Implementation anhand der 'Rechte-Hand-Regel' wäre zwar einfacher zu
  132. verwirklichen gewesen, aber bei weitem nicht so effizient. Es bestünde
  133. vor allem die Gefahr, daß ein solcher Algorithmus in einer Endlosschleife
  134. hängen bleibt, wenn davon ausgegangen wird, daß es in dem Labyrinth keine
  135. Elemente gibt, die nicht mit dem Rest des Labyrinthes in Verbindung stehen,
  136. und genau das kann von der derzeitigen Initialisierung des Labyrinths nicht
  137. geleistet werden. Abgesehen davon ist der derzeitige Algorithmus nicht für
  138. diese Art von Labyrinthen geeignet (siehe unten...). Ich bin während der
  139. eigentlichen Codierung leider etwas von meinen Vorstellungen abgewichen
  140. und habe eher ein Programm geschrieben, das in der Lage ist, komplexe
  141. Hindernisse bestmöglich umgehen zu können.
  142.  
  143.   Das Ergebnis einer Backtracking-Funktion hängt von den Ergebnissen der/des
  144. rekursiven Aufruf(e) ihrer selbst ab. Das bedeutet außerdem, daß eine klar
  145. definierte Abbruchbedingung vorhanden sein muß: in 'Possible' wird die Suche
  146. abgebrochen, wenn der Benutzer den Suchprozeß manuell (mittels Escape)
  147. unterbricht, der Suchalgorithmus keinen Weg zum Zielpunkt finden konnte oder
  148. der Zielpunkt gefunden wurde. Es wird nur nach einer Lösung gesucht, und
  149. zwar der mit dem kürzesten Weg. Um die Suche nach einem Weg zum Zielpunkt
  150. (definiert durch die Parameter fx, fy) so kurz wie möglich zu halten, wurde
  151. die Reihenfolge der Suchvorgänge ausgehend von einem Punkt im Labyrinth
  152. dahingehend optimiert, daß abhängig von der Position (ax, ay) im Verhältnis
  153. zur Position des Zielpunkts (fx, fy) versucht wird, die Distanz zwischen den
  154. beiden Punkten so effektiv wie möglich zu verringern.
  155.  
  156. --------------------------------------------------------------------------
  157.                   Aufbau der graphischen Demonstration
  158. --------------------------------------------------------------------------
  159.  
  160. Es werden maxSize * maxSize rechteckige Felder dargestellt, die im
  161. besten Falle durch ihre 'Wände' voneinander unterscheidbar sind. Das
  162. muß allerdings nicht immer so sein. Der Startpunkt für den
  163. Lösungsalgorithmus ist mit einem grünen, der Zielpunkt mit einem roten
  164. Rechteck markiert. Folgendes ist zu beachten: zwei nebeneinander
  165. liegende Felder können sich überlappende Wände haben (deswegen auch
  166. der Aufwand in 'Possible'). Dieser Fall ist auf dem Bildschirm nicht
  167. erkennbar und auch nicht allzu wichtig, da er von 'Possible'
  168. abgefangen wird, aber man sollte daran denken. Ich hatte es zuerst
  169. nicht getan und mich gewundert, wieso der Algorithmus trotz seiner
  170. scheinbaren Korrektheit 'durch die Wand geht'. Die Suche nach einem
  171. Weg zum Zielpunkt wird grafisch dargestellt. 'Besuchte' Strecken (oder
  172. Positionen) werden farbig (dunkel-blau) markiert. Zum Thema Farben:
  173. BUGS & FEATURES. Alle Strecken, die zu keinem Erfolg geführt
  174. haben, werden nachträglich hell-blau gezeichnet. Die Darstellung ist
  175. vermutlich nicht nachzuvollziehen - Ich habe Sie gewarnt...
  176.  
  177. --------------------------------------------------------------------------
  178.                          BUGS AND FEATURES ( <-: )
  179. --------------------------------------------------------------------------
  180.  
  181. - Die Farbwahl bei der Darstellung wurde mittels 'Gcol' implementiert,
  182.   funktioniert also in 256-Farb-Modi nicht korrekt. Wer sich mit 'Tint'
  183.   auskennt, kann ja mal ergänzen ...
  184.   Die Standard-Farbpalette eines 16-farbigen Modus wird vorausgesetzt.
  185.  
  186. - Die Prozedure 'Possible' braucht enorm viel Stack, da auf jeder
  187.   rekursiven Ausführungsebene eine lokale Tabelle verwaltet werden muß.
  188.   Leider scheint der Compiler nicht in der Lage zu sein, Code zu
  189.   erzeugen, der Stacks über einen gewissem Limit korrekt verwalten kann
  190.   oder Stack-Overflow zuverlässig abfängt!
  191.   Dieser Fehler kann beobachtet werden, wenn man ein Labyrinth der Größe
  192.   100*100 wählt und darauf wartet, daß der Lösungsalgorithmus das ganze
  193.   Feld 'abgrasen' muß, um alle Möglichkeiten ausprobiert zu haben. Der
  194.   Rechner wird vermutlich vollständig 'stehenbleiben'. Das scheint ein
  195.   Bug des Compilers zu sein, da der Fehler unabhängig von der
  196.   konfigurierten Größe des System-Heaps/Stacks auftritt. Dieser Absturz
  197.   (selbst das 'Hourglass'-Modul hängt sich auf) kann jederzeit
  198.   reproduziert werden, da die Applikation zur Erzeugung der 'tLab'-
  199.   Felder immer die gleiche Folge von Zufallszahlen benutzt.
  200.   Eine Lösung des Problems wäre, die für die Richtungen benötigten
  201.   Offsets aus der Tabelle herauszunehmen und im Backtracking-Algorithmus
  202.   für jedes Tabellen-Element einzeln zu berechnen. (=> unübersichtlich)
  203.   Es wäre auch möglich, die Prioritätentabelle durch diverse If-Then-
  204.   Konstruktionen, wie geschehen in Init_Priority zu ersetzen, aber der
  205.   Aufwand wäre im Endeffekt genauso groß oder noch größer.
  206.   Soviel also zum Thema AcornSoft. 'The choice of experience in software'!
  207.  
  208. - Das '.v' (visited) Flag eines Labyrinth-Elementes bestimmt, ob der
  209.   Algorithmus eine bestimmte Strecke 'betreten' darf. Die derzeitige Regel
  210.   besagt, daß eine Position im Labyrinth dann Tabu ist, wenn im einem
  211.   vorherigen Rekursionsdurchlauf die Position schon mal als 'besucht'
  212.   markiert wurde, auch wenn es aus einer anderen Richtung her passierte.
  213.   Das bedeutet, daß eine hinterlassene und noch nicht zurückgenommene
  214.   'Bahn' eines fehlgeschlagenen Lösungsversuches (der das gesamte Labyrinth
  215.   im schlimmsten Fall genau in der Mitte teilt) nicht überkreuzt werden darf
  216.   und ein Weg um einen Endpunkt dieser 'Bahn' herum gesucht werden muß,
  217.   was dann wieder sehr stack-intensiv ist. Eine Möglichkeit, dieses Problem
  218.   zu lösen: in '.v' nicht festhalten, ob die Position überhaupt schon
  219.   besucht wurde, sondern auch, *VON WOHER* oder *WOHIN DANN*. Dies ließe
  220.   sich durch Variabeln realisieren, die Information darüber enthalten,
  221.   aus welcher Richtung das Feld besucht wurde und/oder welches der nächste
  222.   Rekursionsschritt von dieser Position aus ist. Die derzeitige Regelung
  223.   bedingt, daß bei ungünstigen Voraussetzungen nicht der kürzeste Weg durch
  224.   ein Labyrinth gesucht wird, sondern zwangsläufig der längste! Abgesehen
  225.   davon kann die bisherige 'visited'-Abbruchbedingung zu fehlerhaften
  226.   Ergebnissen führen, da es z.B. nicht erlaubt ist, aus einer ein-spurigen
  227.   Sackgasse umzukehren - der einzige Weg aus der Sackgasse wurde schon
  228.   besucht und der als einziger zum Erfolg führende Rekursionsschritt darf
  229.   nicht ausgeführt werden.
  230.     Nach 'links oder rechts zu gehen' bedeutet übrigens nicht, daß sich der
  231.   hypothetische Labyrinth-Läufer (also im Prinzip der Inhalt der Parameter
  232.   eines Rekursionsdurchlaufs) aus einer Richtung um 90° nach links oder
  233.   rechts dreht und dann einen Schritt nach vorne macht. Ganz im Gegenteil
  234.   kennt der Algorithmus nur die vier absoluten Richtungen, in die er sich
  235.   mittels relativer Koordinaten, Offsets bewegen kann. 'Possible' betrachtet
  236.   (ok, ich weiß...) das Labyrinth-Array aus einer Vogel-Perspektive.
  237.  
  238. - Keine Unterstützung des WIMP-Environments. Ist da irgend jemand, der
  239.   etwas Zeit dafür hat? Viel Spaß!
  240.  
  241.  
  242. Name: Stefan Tomlik
  243. Adr.: Im Dachsbau 11
  244. Ort:  59199 Bönen
  245. Tel.: 02383 / 5482
  246.  
  247. internet: tomlik00@marvin.informatik.uni-dortmund.de
  248.